package com.jhy.review.day01;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 求程序遍历的最大宽度 也就是一层当中节点的最多节点的数量
 * 2022年7月20日14:24:29
 */
public class MaximumWidth {
    public static int MaxWidth(Node head) {
        if (head == null) {
            return 0;
        }
        // 定义一个hashmap来存放当前节点的层数
        HashMap<Node, Integer> hashMap = new HashMap<>();
        // 将第一个节点存放进去
        hashMap.put(head, 1);
        // 在定义一个变量知道当前时在哪一层当中
        int curLevel = 1;
        // 定义一个变量知道当前层数有好多个节点的数量，因为head还没有弹出对比 所以我们先设置为0
        int curLevelNode = 0;
        // 计算当中的最大值 先取一个最小值
        int max = Integer.MIN_VALUE;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while (!queue.isEmpty()) {
            // 将当前节点弹出
            Node poll = queue.poll();
            if (curLevel == hashMap.get(poll)) {
                // 在同一层当中的当中的话 就当前层数的节点的数量加1;
                curLevelNode++;
                // max = Math.max(max, curLevelNode); 这里有一个问题就是最后一层的节点无法比较
                // 所以我加入这个来判断一下
                if(poll.left==null && poll.right == null){
                    // 在判断一次
                    max = Math.max(max, curLevelNode);
                }
            } else {
                // 上一层的节点完成了，所以我们比较上一层的数量
                max = Math.max(max, curLevelNode);
                // 如果不在一层当中,那么证明已经在下一层了
                // 所以层数加一
                curLevel++;
                // 当前节点就为1，就是刚刚弹出哪个 所以我们要记录这个节点
                curLevelNode = 1;
            }
            if (poll.left != null) {
                // 左子树为下一层 所以层数要加一
                // 每一次记录当前进去的节点在那一个层当中
                hashMap.put(poll.left, curLevel + 1);
                queue.add(poll.left);
            }
            if (poll.right != null) {
                // 右子树也是这样
                hashMap.put(poll.right, curLevel + 1);
                queue.add(poll.right);
            }
        }
        return max;
    }


}
